//
// Created by Jisam on 2024年10月28日19:33:32
// Solution of P2501 [HAOI2006] 数字序列.cpp
// 2024-10-28 21:16:14 AC 100 线性动态规划 + 最长不下降子序列 
#include <bits/stdc++.h>

#define int long long
#define endl "\n"
#define all(x) (x).begin(),(x).end()
#define pb push_back
using namespace std;

const int MAX_N = 4e5 + 10; // 定义最大序列长度
int a[MAX_N], b[MAX_N]; // 原始序列和调整后的序列
int sum1[MAX_N], sum2[MAX_N]; // 用于存储部分和
int level[MAX_N]; // 存储当前元素所在的层级
int dp[MAX_N]; // 动态规划数组，存储到当前位置的最小改变值
int line[MAX_N], lineIndex; // 线段树，存储调整后的序列值
vector<int> indexList[MAX_N]; // 存储每个层级对应的原始序列索引

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n; // 输入序列长度
    for(int i = 1; i <= n; i++){
        cin >> a[i]; // 输入原始序列
        b[i] = a[i] - i; // 计算调整后的序列值
        dp[i] = LLONG_MAX; // 初始化动态规划数组为无穷大
    }

    int previousIndex;
    for(int i = 1; i <= n; i++){
        if(!lineIndex || line[lineIndex - 1] <= b[i]){
            line[lineIndex++] = b[i]; // 如果线段树为空或当前值小于等于线段树最后一个值，直接添加
            indexList[lineIndex].push_back(i); // 存储当前索引
            level[i] = lineIndex;        
        }else{
            previousIndex = upper_bound(line, line + lineIndex, b[i]) - line; // 查找线段树中第一个大于当前值的位置
            line[previousIndex] = b[i]; // 更新线段树
            indexList[previousIndex + 1].push_back(i); // 存储当前索引
            level[i] = previousIndex + 1;
        }
    }
    cout << n - lineIndex << endl; // 输出最少需要改变的数
    
    indexList[0].push_back(0); // 添加一个虚拟的0索引
    b[0] = -200000; // 设置一个极小值
    level[n + 1] = lineIndex + 1; // 设置一个极值
    b[n + 1] = 200000; // 设置一个极大值
    dp[n + 1] = LLONG_MAX; // 初始化动态规划数组为无穷大
    for(int j = 1; j <= n + 1; j++){
        for(int p = 0 ; p < indexList[level[j] - 1].size(); p++){
            int i = indexList[level[j] - 1][p]; // 获取当前层级对应的原始序列索引
            if(i > j || b[i] > b[j]){
                continue; // 如果当前索引大于j或调整后的值大于j，跳过
            }
            sum1[i] = sum2[j] = 0; // 初始化部分和为0
            for(int q = i + 1; q < j; q++){
                sum1[q] = sum1[q - 1] + abs(b[q] - b[i]); // 计算左侧部分和
            }
            for(int q = j - 1; q > i; q--){
                sum2[q] = sum2[q + 1] + abs(b[q] - b[j]); // 计算右侧部分和
            }
            int minChange = LLONG_MAX; // 初始化最小改变值为无穷大
            for(int k = i; k < j; k++){
                minChange = min(minChange, sum1[k] + sum2[k + 1]); // 更新最小改变值
            }
            dp[j] = min(dp[j], dp[i] + minChange); // 更新动态规划数组
        }
    }
    cout << dp[n + 1] ; // 输出在改变的数最少的情况下，每个数改变的绝对值之和的最小值
    return 0;
}